package cxydmmszl.chapter02.t031;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 按照左右半区的方式重新组合单链表
 * <li style="color: green;">Desc</li>
 * 给定一个单链表的头部节点 head，链表长度为 N，如果 N 是偶数，那么前 N / 2 个节点算作左半区，
 * 后 N / 2 个节点算作右半区；如果 N 为奇数，那么前 N / 2 个节点算作左半区，后 N / 2 + 1个
 * 节点算作右半区。左半区从左到右依次记为 L1->L2->...，右半区从左到右依次记为 R1->R2->...，
 * 请将单链表调整成 L1->R1->L2->R2->... 的形式。
 * <li style="color: green;">Input</li>
 * 单链表的头节点 head。
 * <li style="color: green;">Output</li>
 * 在给定的函数内返回链表的头指针。
 * <li style="color: blue;">Link</li> CD160
 *
 * @author habitplus
 * @since 2021-09-11 10:26
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return 0;
    }

    private static class Node {
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    private static Node readAndGenList(int n) {
        Node tou = new Node(0), pre = tou, node;
        int num;
        for (int i = 0; i < n; i++) {
            num = nextInt();
            node = new Node(num);
            pre.next = node;
            pre = node;
        }

        return tou.next;
    }

    private static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }

    private static void relocate(Node h) {
        if (h == null || h.next == null) return;

        Node mid = h;
        Node right = h.next;

        while (right.next != null && right.next.next != null) {
            mid = mid.next;
            right = right.next.next;
        }

        right = mid.next;
        mid.next = null;
        mergeLR(h, right);
    }

    private static void mergeLR(Node left, Node right) {
        Node nxt;
        while (left.next != null) {
            nxt = right.next;
            right.next = left.next;
            left.next = right;
            left = right.next;
            right = nxt;
        }
        left.next = right;
    }

    public static void main(String[] args) {
        int n = nextInt();
        Node h = readAndGenList(n);

        relocate(h);
        printLinkedList(h);
    }
}
